package com.dataconsruct.skiplist;
import java.util.*;



/**
 * 抄的：https://gitee.com/wcz999/skip-list/tree/master
 */
public class SkipList {

    // 头节点
    SkipListNode header;
    // 尾节点
    SkipListNode tail;
    // 节点个数（不计头节点）
    int length;
    // 层数
    int level;

    // 最大层数
    private static final int MAX_LEVEL = 32;

    // 升层的概率
    private static final double PROBABILITY = 0.25;

    // 最小分值（头节点的分值）
    private static final int MIN_SCORE = Integer.MIN_VALUE;

    private static class SkipListNode {
        // 节点的分数（决定节点的排序）
        int score;
        // 节点的值
        Object obj;
        // 后退指针
        SkipListNode backward;
        // 节点的层
        SkipListLevel[] levels;

        public SkipListNode(int score, Object obj, int level) {
            this.obj = obj;
            this.score = score;
            this.levels = new SkipListLevel[level];
            for (int i = 0; i < this.levels.length; i++) {
                this.levels[i] = new SkipListLevel();
            }
        }

        @Override
        public String toString() {
            return "{" +
                    "score=" + score +
                    ", obj=" + obj +
                    ", level=" + levels.length +
                    '}';
        }
    }

    private static class SkipListLevel {
        // 前进指针
        SkipListNode forward;
        // 跨度(前往当前层的下一个节点，在需要经过多少个节点)
        int span;
    }

    public SkipList() {
        this.header = new SkipListNode(MIN_SCORE, null, MAX_LEVEL);
        this.level = 1;
        this.length = 0;
    }

    // 生成[1,32]之间的随机数作为新节点的层数(符合幂次定律：越大的值生成的概率越小)
    private int getRandLevel() {
        int level = 1;
        Random random = new Random();
        while ((random.nextInt() & 0xFFFF) <= PROBABILITY * 0xFFFF) {
            level++;
        }
        return Math.min(level, MAX_LEVEL);
    }

    // 比较两个对象
    private int compare(Object o1, Object o2) {
        return o1.hashCode() - o2.hashCode();
    }

    // 插入节点
    public void insert(int score, Object obj) {
        // 每层经过的节点个数，用于计算新节点的跨度
        int[] rank = new int[MAX_LEVEL];

        // 待更新的节点(插入的前置节点 或 该层没有插入节点,但需要修改跨度的节点)
        SkipListNode[] update = new SkipListNode[MAX_LEVEL];

        SkipListNode node = this.header;
        for (int i = this.level - 1; i >= 0; i--) {
            // 继承上一层经过的节点数
            rank[i] = (i == this.level - 1) ? 0 : rank[i + 1];
            // 查找当前层的修改位置,并记录每次经过的节点个数
            /* 查找规则：
                  从头到尾遍历该层的所有结点，找到符合以下任意条件的节点
                  1.score最接近新节点，但不大于它的节点
                  2.score与新节点相同，但obj最接近新节点，但不大于它的节点
             */
            while (node.levels[i].forward != null &&
                    (score > node.levels[i].forward.score ||
                            (score == node.levels[i].forward.score && compare(obj, node.levels[i].forward.obj) > 0))) {
                // 记录沿途跨越了多少个节点
                rank[i] += node.levels[i].span;
                // 移动到下一个指针
                node = node.levels[i].forward;
            }
            update[i] = node;
        }

        // 获取随机值作为新节点的层数
        int level = getRandLevel();

        // 如果新节点的层数大于当前跳表的层数，则需要对新的层数进行初始化
        if (level > this.level) {
            for (int i = this.level; i < level; i++) {
                update[i] = this.header;
                update[i].levels[i].span = this.length;
            }
            this.level = level;
        }

        // 创建新节点
        SkipListNode newNode = new SkipListNode(score, obj, level);

        // 将新节点连接到跳表的每一层中
        for (int i = 0; i < level; i++) {
            if (i == update.length || newNode.levels.length == 0 || newNode.levels.length == i) {
                System.out.println(123);
            }
            // 插入新节点
            newNode.levels[i].forward = update[i].levels[i].forward;
            update[i].levels[i].forward = newNode;
            // 计算前置节点和新节点的跨度
            newNode.levels[i].span = update[i].levels[i].span - (rank[0] - rank[i]);
            update[i].levels[i].span = rank[0] - rank[i] + 1;
        }

        // 如果新节点的层数比跳表节点的层数要少，则需要修改没有更新的层
        for (int i = level; i < this.level; i++) {
            update[i].levels[i].span++;
        }

        // 设置回退指针
        node.backward = (update[0] == this.header) ? null : update[0];
        if (node.levels[0].forward == null) {
            this.tail = node;
        } else {
            node.levels[0].forward.backward = node;
        }
        this.length++;
    }

    public void show() {
        for (int i = 0; i < this.level; i++) {
            SkipListNode node = this.header.levels[i].forward;
            while (node != null) {
                System.out.print(node);
                node = node.levels[i].forward;
                if (node != null) {
                    System.out.print("->");
                }
            }
            System.out.println();
        }
    }

}

